#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

 

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：

输入：nums = [1], target = 1
输出：1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/target-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */


int sizer = 0;

void findTargetSumWaysBack(vector<int> &nums, int target, int sum, int startIndex) {
    if (sum > target)
        return;
    if (sum == target) {
        sizer++;
        //return; 我擦retrn 什么时候+ 什么时候不加啊 //TODO 似乎区别不大啊 ret 不ret
    }

    for (int i = startIndex; i < nums.size(); ++i) {

        findTargetSumWaysBack(nums, target, sum + nums[i], i + 1);

    }


}
//既然为target，那么就⼀定有 left组合 - right组合 = target。
//left + right等于sum，⽽sum是固定的。
//公式来了， left - (sum - left) = target -> left = (target + sum)/2 。
//target是固定的，sum是固定的，left就可以求出来。
//此时问题就是在集合nums中找出和为left的组合。

int findTargetSumWays(vector<int> &nums, int target) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (target > sum) return 0;
    if ((target + sum) % 2) return 0; // 此时没有⽅案，两个int相加的时候要各位⼩⼼数值
    int bagSize = (target + sum) / 2; // 转变为组合总和问题，bagsize就是要求的和 灵魂啊

    //为什么抓换成 target+sum 然后除以2

    findTargetSumWaysBack(nums, bagSize, 0, 0);

    return sizer;
}


//第二种方式 dp 也需要 left - (sum - left) = target -> left = (target + sum)/2 。 这个公式、
//TODO 还有 怎么获取那个次数
//dp[][]=
//int findTargetSumWays1(vector<int> &nums, int target) {
//    int sum = accumulate(nums.begin(), nums.end(), 0);
//
//    if (target > sum)return 0;
//    if ((S + sum) % 2 == 1) return 0; // 此时没有⽅案
//    int left = (sum + target) / 2;//获取
//
//    if ()
//
//
//}

/*
 * TODO 这个不太懂说真的
 * /*
        类01背包问题:
        设pos为取+的数字和,neg为取-的数字和(均为正数),则target=pos-neg=pos-(sum-pos)=2*pos-sum
        故pos=(sum+target)/2>=0且为常数,因此此问题等价于求有多少种方式用nums[i]凑成和为pos
        进而该问题抽象为:用价值与体积均为nums[i]的物品,恰好凑满容量为pos的背包方案数
        1.状态定义:dp[j]为恰好能凑满容量为j的背包方案数
        2.状态转移:背包容量能或者不能装下nums[i]
            2.1 当不能装下nums[i]时,方案数直接继承之前的dp[j]
            2.2 当能装下nums[i]时,总的方案数为不考虑nums[i]的方案数+有nums[i]参与新增的方案数
                dp[j] += dp[j - nums[i]],dp[j - nums[i]]种方案与nums[i]共同凑成pos,即1*dp[j - nums[i]]
        3.状态初始化:dp[0]=1,因为后面总会一直查找至j=0,如dp[3] += dp[3-3],空集是任意一条有效路径的起点,当属一条
        4.遍历顺序:i正序,j倒序
        5.返回形式:dp[pos]就是凑成pos总的方案数
         */
int findTargetSumWays11(vector<int> &nums, int S) {
    int sum = 0;
    for (int i = 0; i < nums.size(); i++) sum += nums[i];
    if (S > sum) return 0; // 此时没有⽅案
    if ((S + sum) % 2 == 1) return 0; // 此时没有⽅案
    int bagSize = (S + sum) / 2;
    vector<int> dp(bagSize + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < nums.size(); i++) {
        for (int j = bagSize; j >= nums[i]; j--) {
            dp[j] += dp[j - nums[i]];
        }
    }
    return dp[bagSize];
}